package com.kevin.Code.Heap;

import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * 滑动窗口
 *
 * @author Vinlee Xiao
 * @Classname SlidingWindowMaximum
 * @Description Leetcode 239. 滑动窗口最大值 堆 二刷
 * @Date 2022/3/1 9:50
 * @Version 1.0
 */
public class SlidingWindowMaximum {

    /**
     * 方法一:
     * 堆的思路
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow1(int[] nums, int k) {
        int len = nums.length;
        //最终的结果数组
        int[] result = new int[len - k + 1];

        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[0] - o1[0];
            }
        });

        int cnt = 0;
        for (int i = 0; i < len; i++) {
            queue.add(new int[]{nums[i], i});

            if (i >= k - 1) {
                //得到滑动窗口最左边的坐标
                int leftIndex = i - k + 1;
                while (!queue.isEmpty() && queue.peek()[1] < leftIndex) {
                    //优先队列出队
                    queue.poll();
                }
                result[cnt++] = queue.peek()[0];

            }
        }

        return result;
    }

    /**
     * 方法二:思路和方法一差不多 保持对头 为最大元素
     * 单调栈
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow2(int[] nums, int k) {
        int len = nums.length;
        //最终的结果数组
        int[] result = new int[len - k + 1];

        //用于存储的数组 其中第一个为[数,下标]
        Deque<int[]> queue = new LinkedList<>();
        //用于记录结果数组的下标
        int cnt = 0;
        for (int i = 0; i < len; i++) {

            while (!queue.isEmpty() && nums[i] > queue.peekLast()[0]) {
                //将最后的元素出队
                queue.pollLast();
            }
            queue.addLast(new int[]{nums[i], i});

            int leftIndex = i - k + 1;
            while (!queue.isEmpty() && queue.peekFirst()[1] < leftIndex) {
                queue.pollFirst();
            }

            if (i >= k - 1) {
                result[cnt++] = queue.peekFirst()[0];
            }
        }


        return result;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1};
        SlidingWindowMaximum slidingWindowMaximum = new SlidingWindowMaximum();
        int[] res = slidingWindowMaximum.maxSlidingWindow2(nums, 1);
        for (int i : res) {
            System.out.print(i + " ");
        }
    }
}
